package com.ygu.Enter2;

import java.util.HashSet;

public class HasCycle {
    public boolean hasCycle(ListNode head) {
        return hasCyclyByPointer(head);
    }
    public boolean hasCyclyByPointer(ListNode head){
        //使用快慢指针的方式进行前进
        ListNode fast = head;
        ListNode slow = head;

        while (fast!=null && fast.next!=null){
            slow = slow.next;
            fast = fast.next.next;

            //如果两指针进行相遇则代表有环
            if (slow == fast) {
                return true;
            }
        }
        return  false;
    }

    public boolean hasCycleByHash(ListNode head) {
        //对于判断链表是否存在环的问题 可以使用hash 但是效率不高
        ListNode pos  = head;
        HashSet<ListNode> hashNode = new HashSet<>();

        while (pos!=null){
            if(hashNode.contains(pos)){
                return true;
            }else {
                hashNode.add(pos);
            }
            pos = pos.next;
        }
        return false;
    }

    static class ListNode {
        public int val;
        public ListNode next;

        ListNode(int x) {
            val = x;
            next = null;
        }
    }
}
